﻿#define _CRT_SECURE_NO_WARNINGS
// ↑ 将本行在代码放在第一行可以避免 scanf的报错问题（仅在VS编译器里）
//【学习记录】
//【初阶】35.OJ练习1-链表分割
//【初阶】36.OJ练习2-回文结构判断
//【初阶】37.OJ练习3-链表相交
//【初阶】38.休息
//【初阶】39.OJ练习4-环形链表



//【头文件包含】
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//【自定义声明】
#define LNdatatype int

//【结构体声明】
/*链表结构体*/ typedef struct ListNode
{
	LNdatatype data;
	struct ListNode* next;
}LN;



//【函数声明】
LN* ListNodeCreat();
LN* ListNodeCreat2();
LN* ListNodeCreat3();

LN* ListNodePrint(LN* head);
void SingleListDestory(LN** pphead);
LN* partition(LN* phead, int x);
bool chkPalindrome(LN* phead);
LN* FindFirstCommonNode(LN* pHead1, LN* pHead2);
LN* FindFirstCommonNode2(LN* pHead1, LN* pHead2);
LN* EntryNodeOfLoop(LN* pHead);
//【主函数】
int main()
{
	//OJ题目练习1
	{
		printf("***练习1:链表分割*********************************************************************************\n");
		printf("***给链表头指针，ListNode*phead，给定值x,将小于x的节点排在其余节点之前，且不改变排列后大于值和 ***\n");
		printf("***返回重新排列后的链表头指针。示例：{2,4,5,3,1,2,6,1,4}，3 ->{2,1,2,1,4,5,3,6,4}              ***\n");
		printf("**************************************************************************************************\n");

		LN* plist = ListNodeCreat();
		ListNodePrint(plist);

		plist = partition(plist,4);
		ListNodePrint(plist);
		
		//销毁空间
		SingleListDestory(&plist);
		printf("\n");
	}
	//OJ题目练习2
	{
		printf("***练习2:链表回文结构（对称结构）*****************************************************************\n");
		printf("***对于一个链表，请设计一个时间复杂度为O(n), 额外空间复杂度为O(1)的算法，判断其是否为回文结构。***\n");
		printf("***给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。    ***\n");
		printf("***测试样例：1->2->2->1   返回ture                                                             ***\n");
		printf("**************************************************************************************************\n");
		LN* plist = ListNodeCreat2();
		ListNodePrint(plist);
		if (chkPalindrome(plist))printf("true\n");
		else printf("false\n");
		ListNodePrint(plist);
		plist = ListNodeCreat3();
		ListNodePrint(plist);
		if (chkPalindrome(plist))printf("true\n");
		else printf("false\n");
		ListNodePrint(plist);

		//销毁空间
		SingleListDestory(&plist);

		//更优化的方式，先遍历找到中点
		//利用中间地址执行逆置程序
		//再依次比对
		//最后再从中点逆置一次
		printf("\n");
	}
	//OJ题目练习3
	{
		printf("***练习3:相交链表***************************************************************\n");
		printf("***输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空***\n");
		printf("***测试样例：{1,2,3},{4,5},{6,7}  返回{6,7}                                  ***\n");
		printf("********************************************************************************\n");
		//生成交叉链表用例
		LN* a1 = (LN*)malloc(sizeof(LN));LN* a2 = (LN*)malloc(sizeof(LN));
		LN* b1 = (LN*)malloc(sizeof(LN));LN* b2 = (LN*)malloc(sizeof(LN));LN* b3 = (LN*)malloc(sizeof(LN));
		LN* c1 = (LN*)malloc(sizeof(LN));LN* c2 = (LN*)malloc(sizeof(LN));LN* c3 = (LN*)malloc(sizeof(LN));

		a1->data = 1;a2->data = 2;
		b1->data = 1;b2->data = 3;b3->data = 5;
		c1->data = 7;c2->data = 8;c3->data = 9;

		a1->next = a2;a2->next = c1;
		b1->next = b2;b2->next = b3;b3->next = c1;
		c1->next = c2;c2->next = c3;c3->next = NULL;
		//运行函数
		LN* plist = ListNodeCreat3();
		printf("测试用例1\n");
		ListNodePrint(a1);
		ListNodePrint(b1);
		LN* ret = FindFirstCommonNode(a1, b1);
		ListNodePrint(ret);
		printf("测试用例2\n");
		ListNodePrint(a1);
		ListNodePrint(plist);
		ret = FindFirstCommonNode(a1, plist);
		ListNodePrint(ret);
		ret = FindFirstCommonNode2(a1, b1);
		ListNodePrint(ret);
		//销毁空间
		SingleListDestory(&plist);
		b3->next = NULL;
		SingleListDestory(&a1);
		SingleListDestory(&b1);
		printf("\n");
	}

	//OJ题目练习4
	{
		printf("***练习4:环形链表***************************************************************\n");
		printf("***给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则返回null ***\n");
		printf("***测试样例：{1,2},{3,4,5}  返回3                                            ***\n");
		printf("********************************************************************************\n");
		//生成环形链表用例
		LN* a1 = (LN*)malloc(sizeof(LN)); LN* a2 = (LN*)malloc(sizeof(LN)); LN* a3 = (LN*)malloc(sizeof(LN));
		LN* b1 = (LN*)malloc(sizeof(LN)); LN* b2 = (LN*)malloc(sizeof(LN));
		a1->data = 1; a2->data = 2; a3->data = 3;
		b1->data = 4; b2->data = 5;
		a1->next = a2; a2->next = a3; a3->next = b1;
		b1->next = b2; b2->next = a3; 
		//运行函数
		LN* ret = EntryNodeOfLoop(a1);
		if (ret == NULL)printf("NULL\n");
		else printf("%d\n", ret->data);

		printf("\n");
	}

	return 0;
}



//【函数】}
/*链表测试用例（乱序、偶）*/LN* ListNodeCreat()
{
	LN* plist1 = (LN*)malloc(sizeof(LN));
	LN* plist2 = (LN*)malloc(sizeof(LN));
	LN* plist3 = (LN*)malloc(sizeof(LN));
	LN* plist4 = (LN*)malloc(sizeof(LN));
	LN* plist5 = (LN*)malloc(sizeof(LN));
	LN* plist6 = (LN*)malloc(sizeof(LN));

	plist1->data = 2;
	plist2->data = 1;
	plist3->data = 3;
	plist4->data = 6;
	plist5->data = 5;
	plist6->data = 2;

	plist1->next = plist2;
	plist2->next = plist3;
	plist3->next = plist4;
	plist4->next = plist5;
	plist5->next = plist6;
	plist6->next = NULL;

	return plist1;
}
/*链表测试用例（回文、偶）*/LN* ListNodeCreat2()
{
	LN* plist1 = (LN*)malloc(sizeof(LN));
	LN* plist2 = (LN*)malloc(sizeof(LN));
	LN* plist3 = (LN*)malloc(sizeof(LN));
	LN* plist4 = (LN*)malloc(sizeof(LN));
	LN* plist5 = (LN*)malloc(sizeof(LN));
	LN* plist6 = (LN*)malloc(sizeof(LN));

	plist1->data = 1;
	plist2->data = 2;
	plist3->data = 3;
	plist4->data = 3;
	plist5->data = 2;
	plist6->data = 1;

	plist1->next = plist2;
	plist2->next = plist3;
	plist3->next = plist4;
	plist4->next = plist5;
	plist5->next = plist6;
	plist6->next = NULL;

	return plist1;
}
/*链表测试用例（升序、奇）*/LN* ListNodeCreat3()
{
	LN* plist1 = (LN*)malloc(sizeof(LN));
	LN* plist2 = (LN*)malloc(sizeof(LN));
	LN* plist3 = (LN*)malloc(sizeof(LN));
	LN* plist4 = (LN*)malloc(sizeof(LN));
	LN* plist5 = (LN*)malloc(sizeof(LN));
	//LN* plist6 = (LN*)malloc(sizeof(LN));
	//LN* plist7 = (LN*)malloc(sizeof(LN));
	//LN* plist8 = (LN*)malloc(sizeof(LN));
	//LN* plist9 = (LN*)malloc(sizeof(LN));
	//LN* plist10 = (LN*)malloc(sizeof(LN));



	plist1->data = 1;
	plist2->data = 3;
	plist3->data = 7;
	plist4->data = 8;
	plist5->data = 9;
	/*plist6->data = 5;
	plist7->data = 5;
	plist8->data = 5;
	plist9->data = 5;
	plist10->data = 5;*/


	plist1->next = plist2;
	plist2->next = plist3;
	plist3->next = plist4;
	plist4->next = plist5;
	plist5->next = NULL;
	/*plist6->next = plist7;
	plist7->next = plist8;
	plist8->next = plist9;
	plist9->next = plist10;
	plist10->next = NULL;*/
	return plist1;
}

/*链表打印*/LN* ListNodePrint(LN* phead)
{
	LN* cur = phead;
	while (cur!=NULL)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
/*单链表动态内存空间销毁*/void SingleListDestory(LN** pphead)
{
	//判断传进来的指针是否为空
	assert(pphead != NULL);
	//删除
	LN* cur = *pphead;
	LN* next = *pphead;
	while (cur != NULL)
	{
		
		next = cur->next;
		free(cur);
		cur = next;
		
	}
	*pphead = NULL;
}

/*链表分割*/LN* partition(LN* phead,int x)
{
	LN* cur = phead;
	//较小链表//哨兵位
	//LN* lessHead = (LN*)malloc(sizeof(LN));
	//LN* lessTail = lessHead;
	//lessTail->next = NULL;
	////较大链表//哨兵位
	//LN* greaterHead = (LN*)malloc(sizeof(LN));
	//LN* greaterTail = greaterHead;
	//greaterTail->next = NULL;
	LN* lessHead, * lessTail, * greaterHead, * greaterTail;
	lessHead = lessTail= (LN*)malloc(sizeof(LN));
	lessTail->next = NULL;
	greaterHead= greaterTail= (LN*)malloc(sizeof(LN));
	greaterTail->next = NULL;

	while(cur)
	{
		if (cur->data < x)
		{
			lessTail->next = cur;
			lessTail = cur;
		}
		else
		{
			greaterTail->next = cur;
			greaterTail = cur;
		}
		cur = cur->next;
	}
	lessTail->next = greaterHead->next;

	LN* newhead = lessHead->next;
	greaterTail->next = NULL;
	free(lessHead);
	free(greaterHead);
	return newhead;
}
/*判断回文*/bool chkPalindrome(LN* phead)
{
	//生成快慢指针
	LN* pf = phead;
	LN* ps = phead;
	//记录头指针
	LN* RM = phead;
	//生成头插后新头指针
	LN* newhead = NULL;
	//以快指针为判断，执行头插逆置
	while (pf && pf->next)
	{
		pf = pf->next->next;
	
		LN* next = ps->next;
		ps->next = newhead;
		newhead = ps;
		ps = next;
	}

	RM->next = ps;
	LN* new2 = newhead;
	//区分情况，单数情况下慢指针结束时在中间单一节点，向后再走一步
	if (pf != NULL)
	{
		ps = ps->next;
	}
	//以慢指针为判断继续向后执行依次比较逆置后的前半段和后半段节点
	bool ret = true;
	while (ps)
	{
		if (newhead->data != ps->data)
		{
			//return false;
			ret = false;
			break;
		}
		newhead = newhead->next;
		ps = ps->next;
	}
	//恢复原链表
	ps = new2;
	pf = new2;
	RM = new2;
	newhead = NULL;
	while (pf && pf->next)
	{
		pf = pf->next->next;

		LN* next = ps->next;
		ps->next = newhead;
		newhead = ps;
		ps = next;
	}
	RM->next = ps;
	
	return ret;
	//return true;
}
/*寻找交叉点（O（N^2））*/LN* FindFirstCommonNode(LN* pHead1, LN* pHead2)
{
	LN* cur1 = pHead1;
	//LN* cur2 = pHead2;
	while (cur1)
	{
		LN* cur2 = pHead2;
		while (cur2)
		{
			if (cur1->next == cur2->next)
			{
				return cur2->next;
			}
			cur2 = cur2->next;
		}
		cur1 = cur1->next;
	}
	return NULL;
}
/*寻找交叉点（O（N））*/LN* FindFirstCommonNode2(LN* pHead1, LN* pHead2)
{
	LN* cur1 = pHead1;
	LN* cur2 = pHead2;
	int n1 = 1;
	int n2 = 1;
	while (cur1->next)
	{
		n1++;
		cur1 = cur1->next;
	}
	while (cur2->next)
	{
		n2++;
		cur2 = cur2->next;

	}
	if (cur1 != cur2)
	{
		return NULL;
	}

		int st = abs(n1 - n2);
		LN* longlist = n1 > n2 ? pHead1 : pHead2;
		LN* shortlist = n1 < n2 ? pHead1 : pHead2;
		while (st--)
		{
			longlist = longlist->next;		
		}
		while (longlist != shortlist)
		{
			longlist = longlist->next;
			shortlist = shortlist->next;
		}

		return longlist;
}
/*判断环形链表*/LN* EntryNodeOfLoop(LN* pHead)
{
	//创建快慢指针
	LN* pf = pHead;
	LN* ps = pHead;
	LN* head = pHead;
	
	while (pf && pf->next)
	{
		pf = pf->next->next;
		ps = ps->next;
		if (pf == ps)
		{
			LN* meet = ps;
			while (meet != head)
			{
				meet = meet->next;
				head = head->next;
			}
			return meet;
		}
	}
	return NULL;
}

//【笔记】
